#include <stdio.h>
#include <stdlib.h>

/*
 * 普里姆：最小生成树
 */

#define vertex_max 6 // 网上顶点数
#define edge_max 10	// 网中边数

struct edgeset	// 定义一条生成树的边
{
  int fromvex;	// 边的起点
  int endvex;	// 边的终点
  int weight;	// 边上的权值
};

struct tree
{
  int s[vertex_max + 1][vertex_max];	// 网的邻接矩阵
  struct edgeset ct[vertex_max + 1];	// 最小生成树的边集
};

void prim(struct tree * tree)
{
  int i, j, k, min, t1, m, w;
  struct edgeset temp;

  for (i = 1; i <= vertex_max; i++) {	// 从顶点1出发求最小生成的树边
    tree->ct[i].fromvex = 1;
    tree->ct[i].endvex = i + 1;
    tree->ct[i].weight = tree->s[1][i+1];
  }

  for (k = 2; k <= vertex_max; k++) {
    min = 32767;
    m = k - 1;
    
    for (j = k - 1; j < vertex_max; j++) 	// 找权值最小的树边
      if (tree->ct[j].weight < min) {
	min = tree->ct[j].weight;
	m = j;
      }
    
    temp = tree->ct[k-1];
    tree->ct[k-1] = tree->ct[m];
    tree->ct[m] = temp;
    j = tree->ct[k-1].endvex;
    
    for (i = k; i < vertex_max; i++) {	// 重新修改树边的距离
      t1 = tree->ct[i].endvex;
      w = tree->s[j][t1];
      if (w < tree->ct[i].weight) {	// 原来的边用权值较小的边取代
	tree->ct[i].weight = w;
	tree->ct[i].fromvex = j;
      }
    }
  }
}

void display(struct tree * tree, int vexter)
{
  int i, j, count;

  count = 0;
  for (i = 1; i <= vertex_max; i++)
    for (j = 1; j <= vertex_max; j++) {
      printf(" %d ", tree->s[i][j]);
      count++;
      if (count % vexter == 0) 
	printf("\n");
    }

  printf("\n");
}

void main()
{
  int i, k, j, w;
  struct tree tree;

  for (i = 1; i <= vertex_max; i++)
    for (j = 1; j <= vertex_max; j++)
      if (i == j)
	tree.s[i][j] = 0;
      else 
	tree.s[i][j] = 32767;

  for (k = 1; k <= edge_max; k++) {
    printf("input a edge and edge of quan number:\n");
    scanf("%d %d %d", &i, &j, &w);
    tree.s[i][j] = w;
    tree.s[j][i] = w;
  }

  prim(&tree);
  display(&tree, vertex_max);

  for (i = 1; i < vertex_max; i++) {	// 输出n-1条生成树的边
    printf("fromvex = %d ", tree.ct[i].fromvex);
    printf("endvex  = %d ", tree.ct[i].endvex);
    printf("weight  = %d ", tree.ct[i].weight);
    printf("\n");
  }
}
